package a_doubleWrite;

import java.util.Arrays;

/**
 * todo
 *
 * @author luolidong
 * @version 1.0
 * @create 2021-07-30 08:59
 */
public class HeapSort_1 {
    public void buildHeap(int[] nums) {
        for (int i = (nums.length - 2) / 2; i >= 0; i--) {
            downAdjust(nums, i, nums.length - 1);
        }
    }

    private void downAdjust(int[] nums, int parent, int len) {
        int temp = nums[parent];//记录父节点
        int child = parent * 2 + 1;//左节点位置
        while (child <= len) {
            //判断右节点是否更大
            if (child + 1 <= len && nums[child + 1] > nums[child]) {
                child += 1;//那么记录右节点位置
            }
            //判断是否小于父节点
            if (nums[child] <= nums[parent]) {
                break;
            }
            //让子节点继续迭代
            nums[parent] = nums[child];
            parent = child;
            child = parent * 2 + 1;
        }
        //将原来父节点赋值后面的
        nums[parent] = temp;
    }

    private int[] sort(int[] nums) {
        buildHeap(nums);
        //每次头尾交换，继续下沉
        for (int i = nums.length - 1; i > 0; i--) {
            int temp = nums[0];
            nums[0] = nums[i];
            nums[i] = temp;

            downAdjust(nums, 0, i - 1);
        }
        return nums;
    }

    public static void main(String[] args) {
        HeapSort_1 heapSort_1 = new HeapSort_1();
        int[] sort = heapSort_1.sort(new int[]{2, 1, 4, 3, 2, 5});
        System.out.println("Arrays.toString(sort) = " + Arrays.toString(sort));
    }
}
